For questions about the study of finite or countable discrete structures, specifically how to count or enumerate elements in a set (perhaps of all possibilities) or any subset. It includes questions on permutations, combinations, bijective proofs, and generating functions.

learn more… | top users | synonyms (4)

1
vote
2answers
54 views
6
votes
3answers
88 views

Probability of choosing $n$ numbers from $\{1, \dots, 2n\}$ so that $n$ is 3rd in size

We uniformly randomly choose $n$ numbers out of $2n$ numbers from the group $\{1, \dots, 2n\}$ so that order matters and repetitions are allowed. What is the probability that $n$ is the $3^{\text{rd}}$...
-6
votes
0answers
26 views

Permutation, Arranging letters [on hold]

Please help me! I am in a hurry! The six letters of the word “MOTHER” are rearranged in all possible orders and the words so formed are listed in alphabetical order
1
vote
1answer
30 views

Proving an inequality about a set of combinations.

Suppose $A$ is a set of $r$ combinations of an $n$ set, with $\alpha \cap \beta \neq \phi$, whenever $\alpha, \beta \in A$. Show that $$|A| \leq \binom{n-1}{r-1}$$ if $r \leq \frac n2$. What does ...
3
votes
3answers
99 views

Number of positive unequal integer solutions of $x+y+z+w=20$

What is the number of positive different integer solutions of $x+y+z+w=20$, where $x,y,z,w$ are all different and positive? It would be nice if coding is not used. I am given the answer $552$.
0
votes
2answers
32 views

Number of permittable numbers given following conditions.

What are total numbers belonging to $\mathbb Q$ (rational) between $2008$ and $2009$ such that after decimal point their digits occur in decreasing order? \begin{align} 1) &\ 9Pi;i\in [1,9], \\ 2)...
5
votes
1answer
166 views

Number Theory Characterization Problem

Given any natural number $N = a_{n}a_{n-1}\ldots a_{1}$, let us associate to it the set $S_{N} = \bigcup_{j=1}^{n}\{(a_{j},j)\}$. We're going to define a d-self-contained number as any natural number ...
0
votes
0answers
22 views

Prove that if B(0) = 0, then A(B(x)) is a formal power series

I'm working through my Combinatorics textbook and am stuck on this proof. The textbook explains it pretty well, but I am having trouble with one of the steps. I was hoping I could get some help here ...
0
votes
1answer
26 views

Definition of $0^\underline{m}$ for $m\leq0$

Using the general definition of falling powers for negative exponents, I was able to derive $$0^{\underline{m}} = \frac{1}{(-m)!}, m\leq0$$ However, I can't reconcile this with the product formula $$0^...
1
vote
2answers
23 views

Constructing Turan Graphs

A "Turan Graph " on $n$ vertices is graph on $n$ vertices without triangles and with exactely $\lfloor \frac{n^2}{4}\rfloor$ edges. How many are the Turan Graphs on $8$ vertices? There's an easy ...
0
votes
1answer
24 views

Approaches to combining analysis with combinatorics and number theory?

I hope this questions fits the site. I am interested in various methods of combining analysis with combinatorics and number theory. What I mean by this is that (at least to me) at first I wouldn't ...
3
votes
1answer
44 views

$\binom{n}{k}$ is a “binomial coefficient;” $n \; P \; k$ is a “__________.”

If I want to search for information concerning $\binom{n}{k}$, I can't Google that symbol directly, nor can I search for something like "n C k" and get anything relevant, but because the term "...
6
votes
2answers
117 views

The number of positive integer solutions to the equation $x_1+2x_2+…+nx_n=n^2.$

Let $n \ge 2, n \in \mathbb N$. $A_n$ denotes the number of positive integer solutions to the equation $$x_1+2x_2+...+nx_n=n^2.$$ Prove inequality $$\frac{n^n(n-1)^{n-1}}{2^{n-1}\left(n!\right)^...
1
vote
5answers
64 views

Arrange black and white balls so that each pair of white balls is separated by at least two black balls

I am trying to solve the following question: How many linear arrangements of $m$ white balls and $(n-m)$ black balls are possible such that each pair of white balls is separated by at least two ...
7
votes
4answers
165 views

Why does $(128)!$ equal the product of these binomial coefficients $128! = \binom{128}{64}\binom{64}{32}^2 \dots \binom21^{64}$?

I'm working through some combinatorics practice sets and found the following problem that I can't make heads or tails of. It asks to prove the following: $$128! = \binom{128}{64}\binom{64}{32}^2\...
2
votes
1answer
45 views

Binary matrices and probability

Square numerical matrix in which each cell is written or the number $0$ or the number $1$ is called binary. Let $T_n -$ the set of all binary matrix $m\times m, m=2,3,...,n$. Find the probability ...
0
votes
0answers
20 views

Number of nodes satisfying a certain property on a binary tree

Fix a large integer $M$ and construct a binary tree as follows. Assign the root node by the integer $0$. If a node is assigned the integer $n$ and $n \leq M - 2$, then $n$ has two children and ...
0
votes
1answer
19 views

Determining when two binary strings represent the same necklace or when one binary string is periodic

An equivalence relation on binary strings calls two strings equivalent if one can be obtained from the other by a cyclic permutation of the characters. Combinatorialists call the equivalence classes ...
0
votes
1answer
30 views

How would I calculate the total number of combinations [closed]

Lets say I have 4 lines or rows lets call them Row 1 .. Row 4 Now the total number of ways to delete the rows are: Row 1 (leaving Row2, Row3, Row4) Row 2 (leaving Row1, Row3, Row4) Row 3 Row 4 ...
3
votes
1answer
34 views

Generic method to distribute n distinct objects among r people such that each person gets at least one object

Is there any generic method to solve problems of the kind - "How many ways to distribute n distinct objects among r person(s) such that each person gets at least 1 object?". I am aware of 2 different ...
2
votes
3answers
29 views

Number of orbits with Burnside's lemma

We color a equilateral triangle by coloring each edge with one of $k \geq 1$ colors. Find a formula for the number of orbits under the action of $D_6$, the dihedral group of $6$ elements, on the ...
1
vote
0answers
31 views

Congruence numbers

Having read about Stirling numbers of the second kind I am curious. The article says it shows the number of equivalence relations on a set $n$ with $k$ equivalence classes which makes sense to me from ...
0
votes
0answers
36 views

Two variable recurrence relations with conditionals

Is it possible to obtain a generating function for the sequence described by the following recurrence? $$ f(n,m) = \begin{cases} f(n, \thinspace m-1) + f(n-m, \thinspace m-1), & \text{ if } n \...
7
votes
1answer
49 views

Numbers on a circle: how many arc sums can be positive?

There are $n$ real numbers, $a_1,\dots,a_n$, arranged on a circle. Given a fixed integer $k<n$, let $S_i$ be the sum of the $k$ adjacent numbers starting at $a_i$ and counting clockwise, like this (...
0
votes
0answers
49 views

How many strings of 12 lowercase letters with repetitions

Consider strings of 12 lowercase letters, such as aksdjmnuuyio. How many strings either are a repetition of 2 strings of 6, such as aksdjmaksdjm, or a repetition of three strings of 4, such as ...
0
votes
2answers
29 views

Optimising my chances of drawing a specific card from a small deck.

I have a deck of 24 cards, 3 of which are aces. I want to figure out my chances of drawing at least one ace based on the number of cards I draw. I'm pretty sure if I draw one card my chance is 12.5% I'...
1
vote
2answers
25 views

Permutation of coefficient with coditions [closed]

I have 6 coefficients, (V1,V2,H1,H2,D1,D2). Their permutation is 6! = 720. But I have a rule: V2 cannot lead V1, H2 cannot lead H1 and D2 cannot lead D1. For example: V2V1H1H2D1D2 is prohibit. ...
0
votes
1answer
52 views

How to approximate the Langford numbers with probability?

A Langford pairing, also called a Langford sequence is a permutation of the multi set {$1,1,2,2, \dots, n,n$} in such a way that there are exactly $k$ elements in between every $k$. Interestingly, ...
1
vote
3answers
50 views

Combinations of 5 integers from 1 to 100 such that differences between the sorted integers of each combination is at least 5 but not more than 10?

For example , I am trying to count combinations like [1,6,14,21,27] because the minimum difference between two sequential integers in the combination is 5 and the maximum distance is 8, but I don't ...
3
votes
1answer
28 views

Bell numbers and the Moments of expected number of fixed points

Let $X_N$ be the random variable corresponding to the number of fixed points (1-cycles) in a permutation chosen uniformly at random from $S_N$. Then, the $m^{\text{th}}$ moment, when $m < N$, is ...
1
vote
1answer
74 views

longest way to rearrange students before returning to original arrangement? [closed]

This is Q24 from the 2012 Intermediate Australian Mathematics Competition: "A teacher has a class of twelve students. She thinks it would be a nice idea if they change desks every day, so she has ...
2
votes
1answer
65 views

a collection of 20 marbles from infinite pool of 2 color marbles with replacement.. [closed]

I have an infinite supply of pink and blue marbles. Probability that any random draw will yield a pink marble is "p" and prob. of picking blue is 1-p. Let us assume p=0.4 if a numeric value helps. ...
0
votes
3answers
51 views

Counting non-negative integral solutions

I'm reading this passage and wondering why Number of ways in which k identical balls can be distributed into n distinct boxes = $$\binom {k+n-1}{n-1}$$ could someone explain it to me please?
0
votes
0answers
21 views

Is there a faster way of computing the probability of a sum $S$ when $n$ dice are rolled? [duplicate]

So far, I've only had to deal with $2$ dice or $3$ dice problems. For example, if the problem asks to find the probability that a sum of $8$ will be achieved from rolling $3$ dice, I just list all the ...
0
votes
0answers
23 views

number of inversions in permutation if subarray of permutation is reversed?

I have permutation(P) of numbers 1 to N (<=10^5) . Suppose I can reverse the subarray of ...
1
vote
2answers
51 views

There are 10 boxes, 15 balls; 10 red, 5 blue. Each is randomly placed in a box in an independent manner. What's E[X=the number of empty boxes?]

There are 10 boxes, 15 balls; 10 red, 5 blue. Each is randomly placed in a box in an independent manner. The red balls are placed in boxes 1-10, blue balls are placed in 1-6. What is the expected ...
6
votes
3answers
682 views

Prove this using counting techniques: $\sum_{k=0}^{n}{\binom{2n+1}k} = 2^{2n}$

I recently came across a question while studying for an exam. I haven't been able to solve it. We had to prove: $$\sum_{k=0}^{n}{2n+1\choose k} = 2^{2n}$$ We had to use counting techniques. This was ...
9
votes
5answers
174 views

How many arrangements of the letters in the word CALIFORNIA have no consecutive letter the same?

First off, the correct answer is $$584,640 = {10!\over 2!2!}- \left[{9! \over 2!}+{9! \over 2!}\right] + 8!$$ which can be found using the inclusion-exclusion principle. My own approach is different ...
0
votes
2answers
47 views

Prove that a graph has a cycle of length no more than $14$

A graph contains $2016$ vertices, its chromatic number is $5$, prove that this graph has a cycle of length $\leq 14$. Where do I start?
1
vote
0answers
31 views

The relation between Weyl character formula and Frobenius characteristic map

Let $\mathfrak{gl}(n)$ be the general linear Lie algebra of rank $n$, and $\mathfrak{S}_d$ be the symmetric group of rank $d$. It is well-known that the Schur-Weyl duality provide a equivalence ...
0
votes
4answers
37 views

Why doesn't this alternative method work? Chance of getting four of a kind in a hand of $5$ cards?

Please note: This is not a duplicate since it is asking about an alternative method of solving the question What is the probability of getting four of a kind in a hand of $5$ cards from a standard ...
3
votes
2answers
105 views

Find all solutions to $2 x + 3 y + 4 z = 10$

I do not have a background in math, and am wondering what type of question this is. I looked combinatorics optimization, and the knapsack problem, but found the vocabulary too dense. The problem: ...
0
votes
3answers
83 views

How many ways are there to choose 5 ice cream cones if there are 10 flavors?

I had this on a test and I gave answer as: (10 C 5) but it was incorrect. Why? Isn't this just a typical combination problem where you select 5 objects of 10 objects! Correct answer: $_{(10+5−1)}C_{ ...
-1
votes
3answers
50 views

Suppose that an ice-cream café has 10 different flavors of ice cream. [closed]

In how many different ways one can choose 3 scoops of ice-cream, so that order of flavors does not matter?
5
votes
1answer
62 views

On “good” numbers and $m \times n$ real matrices

Let $m,n > 1$ be odd integers. Different real numbers are written in the cells of the $m \times n$ table ($m$ rows and $n$ columns). The number is called "good" if 1) It is the largest in its ...
2
votes
1answer
33 views

Can't understand one chance in R of winning where R is some result of factorials.

In lotto game, let you select six no. from 51 no. on a card and the Lotto managers pick six no. at random. If your choice exactly matches theirs, you win a few dollars. If you have to pick 6 values ...
2
votes
0answers
40 views

The number of partitions of $n$…Subbarao

(Subbarao) The number of partitions of $n$ in which each part appears two, three, or five times equals the number of partitions of $n$ into parts congruent to $2, 3, 6, 9,$ or $10$ modulo $12$. ...
6
votes
3answers
58 views

In how many ways can an inspector visit $4$ normal sites and $1$ “suspicious” one?

I cannot figure out why my answer to the following question is wrong: Suppose that a weapons inspector must inspect each of five different sites twice, visiting one site per day. The inspector is ...
0
votes
3answers
31 views

Find the number of all possible valuations that will satisfy given expression.

This part concerns the 256 possible truth valuations of the following eight propositional letters A, B, C, D, E, F, G, H. For each of the following expressions, say how many of the 256 valuations ...
0
votes
1answer
31 views

Committee selection problem

The problem goes as follows: A committee of $7$ is to be formed from $9$ boys and $4$ girls. In how many ways can this be done when the committee consists of 1. At least $3$ girls? 2. ...