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)

2
votes
4answers
48 views

Interesting probability question - husband and wife committee variation

Twenty husbands and wives (ten couples) are randomly divided into two groups. What is the probability that at exactly 4 wives are in the same group as their husbands? Attempt: There are $\binom{40}{2}...
1
vote
4answers
784 views

How many $3$-digit numbers can be formed so that the sum of two digits will be equal to the third digit?

How many $3$-digit numbers can be formed so that the sum of two digits will be equal to the third digit? I am confused in this question whether to take first 2 digits sum or any digit sum such that ...
7
votes
4answers
183 views

Maximum area of triangle inside a convex polygon

Prove that within any convex polygon of area $A$, there exists a triangle with area at least $cA$, where $c=\tfrac{3}{8}$. Are there any better constants $c$? I'm not sure how to approach this ...
2
votes
1answer
49 views

Sum identity using Stirling numbers of the second kind

Experimenting with series representations of $e^{x e^x}$ I came across the two seemingly different power series $$e^{x e^x} = \sum_{n=0}^{\infty} x^n \sum_{k=0}^{n} \frac{(n-k)^k}{(n-k)! \cdot k!}$$ ...
2
votes
2answers
130 views

Flip cards to get maximum sum

Given N cards where if ith card has number x on its front side then it will have -x on back side and a single operation that can be done only once that is to flip any number of cards in consecutive ...
-3
votes
2answers
40 views

Showing that $\sum\limits_{x=0}^y\frac{x\cdot y!}{x!(y-x)!}=2^{y-1}{y}$ [on hold]

Why is the following true? I keep getting $\frac y2 + y$. What am I missing? $$\sum\limits_{x=0}^y\frac{x\cdot y!}{x!(y-x)!}=2^{y-1}{y}$$
-5
votes
0answers
13 views

Edge covering of line graph over Ring z_10 [on hold]

Line graph of z_10 is complete graph with 4 vertices. Edge covering is one?
0
votes
2answers
28 views

Distribution of 4 distinct balls into 5 identical boxes without any restrictions, order of the balls is important

Find number of ways $4$ distinct balls can be distributed into $5$ identical boxes where any box can contain any number of balls (even empty boxes are allowed) Note that the order of balls ...
0
votes
2answers
35 views

Contradiction in solving recurrence?

Solve the recurrence $u_n = 2u_{n-1}-u_{n-2}$ if $u_0 = 0$ and $u_1 = 1$. The characteristic polynomial gives $x^2-2x+1 = 0 \implies x = 1$ and so $u_n = \lambda_1+\lambda_2$. But since $u_0 = 0$, ...
3
votes
5answers
315 views

Log concavity of binomial coefficients: $ \binom{n}{k}^2 \geq \binom{n}{k-1}\binom{n}{k+1} $

How do we prove that Binomial coefficients are log-concave? A sequence $a_0, \dots, a_n$ is log-concave if $a_k^2 \geq a_{k-1}a_{k+1}$. $$ \binom{n}{k}^2 \geq \binom{n}{k-1}\binom{n}{k+1} $$ If $ n &...
4
votes
1answer
33 views

probability/combinatorics question with marbles

An urn has 20 green out of 50 marbles. Draw all 50 marbles without replacement. Let X = # of green marble runs of any length. Example : GGGGBBBGGBBGBB. . . In the above example, there are 3 runs in ...
1
vote
1answer
32 views

Finding probability with the help of combinations

$N$ tutors are to be assigned to $s$ students with any student having at most one tutor and similarly any tutor having at most one student. If any tutor is assigned randomly then how can we find the ...
1
vote
2answers
18 views

Number of multisets with restrictions on specific element count

I am looking to find the number of multisets with restrictions on the number of specific elements. This isn't for homework, it is a work related problem. My set of items is {A, a, B, b}. I want to ...
1
vote
2answers
55 views

Probability Conjecture

I think there is a flaw in my logic but I'm not sure where it would be. Let HHH denote the event of three coin flips. Let E(HHH) be the expected value of the number of coin flips until HHH. Let E(...
2
votes
0answers
37 views

Is there always $n$ permutations of a vector in $R^n$ that are linearly independent?

As long as the $n$ entries of the vector are all different and they dont add up to zero. If it is true, how to prove it, if not, what is a counter example?
1
vote
1answer
29 views

Locating the double of a number in a triangular arrangement of the integers?

I write the positive numbers starting at $1$ in a triangle:$$\mathbb{N}_\triangle = \begin{matrix} &&&&&21&\ldots \\ &&&&15&20&\ldots ...
0
votes
2answers
19 views

Equal division of unit square tiles without stacking into individual tiles

A chocolate bar having (m X n) unit square tiles is given. How many number of cuts would be needed to break it completely, without stacking, into individual tiles. (m X n) (m-1) X (n-1) (m X n) - ...
0
votes
2answers
31 views

Trouble deriving the Catalan numbers (near the last step)

The final result should be $C(n) = \frac{1}{n+1}\binom{2n}{n}$, for reference. I've worked my way down to this expression in my derivation: $$C(n) = \frac{(1)(3)(5)(7)...(2n-1)}{(n+1)!} 2^n$$ And I ...
0
votes
1answer
34 views

How many sequences with $k$ different values less than $d$?

Pick $\ell$ elements of $\{1,\dots,n\}$ with replacement ($n^\ell$ different ways to do that). Given $k\leq \ell$ and $d\leq n$, in how many cases will you have exactly $k$ different values $\leq d$? ...
1
vote
0answers
33 views

How often is $k, 2k, 3k…$ modulo $n$ less than $b$ before it hits $-1$?

Let $n$ and $k$ be coprime, and let $1\leq b \leq n$. The sequence $k, 2k ,3k, \ldots$ reduced modulo $n$ to the range $1, \ldots, n$, will eventually run through every integer in the range $1, \ldots,...
3
votes
0answers
38 views

Could the classical Ramsey numbers be successors of primes?

Let $R(n)$ denote the classical Ramsey-number, that is, the smallest natural $N$, for which every blue-red edge-colouring of $K_N$ admits a monochromatic $K_n$. Consider the conjecture: $R(n)-1$ is ...
5
votes
0answers
50 views

Interesting property of Fibonacci numbers

Let we have an integer number $m$ such that $p \mid m \implies (p^2-1) \mid m$ for any prime divisor $p$ of $m.$ Prove that for such $m$ we have $F_{n+m}=F_{m} \mod m $ for any $n>1.$ Any ideas ...
0
votes
2answers
29 views

Sum of the series in terms of coefficient of $x^m$ in some binomial expansion.

It is written in my book that: 10C0×20Cm + 10C1×20Cm-1+ ... + 10Cm×20C0 = coefficient of $x^m$ in the expansion of $(1+x)^{10}(1+x)^{20}$. I'm in doubt how this happened.
2
votes
0answers
29 views

Who has the strategy of winning?

We have $25$ cards numbered from $1$ to $25$. The first person raises a card and the second one says who is going to get the card. After that, the person that has a higher score (the sum of the ...
1
vote
2answers
27 views

Chance that one random outcome beats another one?

After some studies I´m able to calculate combinations and permutations, but I fail to compare multiple events. Imagine you have 2 groups of fair conis: one group with 3 coins, the other one with 4. ...
1
vote
2answers
31 views

Upper bound to a series with binomial coefficients

Let $c>0$ and $m$ be a positive integer. The following sum is convergent, but how fast does it grow with $m$ as $m$ is large? $$ f(m)= \sum\limits_{n=1}^{\infty} \binom{n + m}{n} e^{-c \, n} $$ ...
0
votes
1answer
22 views

Finding binomial coefficients of product of two binomials

Suppose the expression is given like this: $(1+x) ^{10} (1+x)^{20}$. How can I find out the coefficient of $x^m$ in the above expression, given that $0≤m≤20$.
1
vote
1answer
401 views

Multiple Choice Knapsack Problem (MCKP) where one class requires more than one item

I have the following problem of which I am attempting to find a near optimal solution: I have one knapsack which can hold a maximum weight. I must select exactly one distinct item from a number of ...
0
votes
1answer
73 views

rooted labeled trees with root degree 2

A colleague of mine (who is not a mathematician at all) asks me to have a look at his formula for the number $T_n$ of rooted labeled trees on $n$ vertices where the root has degree 2. He starts out ...
4
votes
0answers
48 views

Combinatorics: 30 people rotating around 6 tables - largest number of different people each person can meet?

Say there are 30 people at an event and six tables (A-F), each seating five people. There are six sessions, and each person must visit each table exactly once. I /think/ that it's impossible for ...
0
votes
1answer
37 views

Prove that in a tree #leaves + #nodes of degree 2 $\geq \frac{n}{2}$

I am trying to solve the following problem: Let $T = (V,E)$ be a Tree with $n = |V|$ nodes. Let $b$ denote the number of leaves and $z$ the number of nodes with degree $2$. I want to show that $$ ...
0
votes
0answers
32 views

Plaid in generic position. Counting faces.

I write $\pi_n$ to denote a group of $n$ parallel lines. Consider a family of $(\pi_1,\pi_2,\ldots,\pi_s)$ parallel groups each with $(n_1,n_2,\ldots,n_s)$ parallel lines. Arrange the family of ...
0
votes
1answer
23 views

Combinatorics problem with n-words

Let $x_{1},...x_{n}$ be different chars I'm making words of length $n$, where $$n=3k, k\in \mathbb{N}$$ I have two questions 1) how many different words are there, with all different characters, that ...
0
votes
0answers
49 views

Proof of identity via binomial theorem

I wonder how to elegantly prove the following identity for all $n\ge 3$: $$\frac{n}{2}\cdot \sum_{x+y=n-1,x\ge 1,y\ge 1}\binom{n-1}{x}x^{x-1}y^{y-1} = n\cdot(n-2)\cdot (n-1)^{n-3} $$ via the ...
0
votes
0answers
26 views

Prove that we can divide the students into $k$ classes satisfying the following conditions

I would appreciate if somebody could help me with the following problem. Q: There are $n$ students each having $r$ positive integers. $nr$ positive integers are all different. Prove that we can ...
1
vote
1answer
23 views

Combinatorial problem on finding the index associated to an edge of a complete graph

Ok so here is a combinatorial problem that I thought of. Suppose N is in $\mathbb N$ such that $N>1$, then there is a way to count (set an index) to all pairs $(i,j) \in \{1,\dots,\mathbb N\}\...
-2
votes
0answers
26 views

Combinatorical problem [on hold]

$k$ is a natural constant.Determine $x,y,z$ knowing that $\binom{z+k}{x+y} + \binom{z}{x} \le k$ and $2x+y \le z$.
0
votes
1answer
43 views

How to find documentation for or a proof of the following known binomial identity

I came across this identity in my research, but have not been able to prove it. When I entered the LHS of the identity in mathematica, to my surprise, it popped out the RHS, which I presume means the ...
0
votes
1answer
51 views

Combinatorics-Number Theory Problem

A positive integer is written on each vertex of a pentagon, a different one on each vertex. On each side is written the $lcm$ of the numbers of the vertices that form that side. If $n$ is written on ...
-3
votes
0answers
33 views

Comp Questions-Enumeration, Rates, Numbers, Geometry [on hold]

For each integer from 0 to 999, Michael wrote down the sum of its digits. What is the average of the numbers that Michael wrote down? It takes Jacob one and a half hours to paint the walls of a room ...
7
votes
3answers
126 views

Number of integer triplets $(a,b,c)$ such that $a<b<c$ and $a+b+c=n$

What is an equivalent combinatorial presentation for the problem? Can I use the stars and bars approach to find the number of integral solutions of $a+b+c=n$ where $a,b,c\geq 0$? If in addition $a+b&...
3
votes
1answer
50 views

Elementary proof for average number of tree components in a random forest of fixed size

In Flajolet's & Sedgewick's "Analytic Combinatorics" I found the statement that for a forest ("Catalan", i.e. collection of ordered trees) of size $n$, uniformly distributed, the number of tree ...
1
vote
1answer
18 views

Un-monochromatic Arithmetic Progressions

Prove that the set $\{1,2,3,...,2008\}$ can be colored with two colors such that any $18$ term arithmetic progression in this set is not monochromatic.
0
votes
1answer
37 views

Reduction from Circuit-Sat to 3-Sat

I'm reading the following notes on reduction from circuit-sat to 3-sat http://www.cs.cmu.edu/~avrim/451f11/lectures/lect1108.pdf On the third page i'm unsure how they arrived at the following In ...
2
votes
4answers
67 views

Probability that the second throw of a fair die exceeds the first

A player throws an ordinary die and records the score $A$. The player then throws the die again and again records the score, $B$. if $B>A$ then we set a score for this player. What is the ...
2
votes
1answer
4k views

Game combinations of tic-tac-toe

How many combinations are possible in the game tic-tac-toe (Noughts and crosses)? So for example a game which looked like: (...
0
votes
0answers
26 views

Upper bound number of self-avoiding walk of length $n$

A self-avoiding walk is a sequence of $n$ neighbor sites on a graph which are all distinct. Let $C_n$ be number of self-avoiding walk of length $n$ in a $d$-dimensional regular lattice. As a ...
1
vote
7answers
190 views

Prove that ${2^n-1\choose k}$ and ${2^n-k\choose k}$ ar always odd. [duplicate]

How can I prove that ${2^n-1\choose k}$ and ${2^n-k\choose k}$ always returns odd numbers? It is possible to prove this by congruence? by the way : $0 \leq k \leq (2^n-1)$
0
votes
0answers
19 views

Quantizing a matrix of reals while preserving row and column sums

Assume $E = [\epsilon_{i,j}]$, $i=1,2,\dotsc,m$, $j=1,2,\dotsc,n$, is an $m\times n$ matrix of reals. We know that $\forall i,j$, $\epsilon_{i,j}\in[-1/2,1/2]$. Moreover we know that both row-sums ...
1
vote
1answer
33 views

Number of $n$-ples of integers summing to a given integer

Fix a non-negative integer $m$. For any integer $A \geq 1$, use $P_m(A)$ to denote the number of ways of rewriting $A = A_1 + A_2 + \ldots A_m$, with $A_i$ non-negative integers (eventually $0$). Is ...